package club.xiaojiawei.greedy;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/30/22 9:40 PM
 * @question 738. 单调递增的数字
 * @description 当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
 * 给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
 */
public class MonotoneIncreasingDigits738 {

    public static void main(String[] args) {
        MonotoneIncreasingDigits738 test = new MonotoneIncreasingDigits738();
        int result = test.monotoneIncreasingDigits(332);
        System.out.println(result);
    }

    /**
     * 贪心
     * 遍历遇递减而返
     * 时间复杂度O(n)
     * 空间复杂度O(1)
     * @param n
     * @return
     */
    public int monotoneIncreasingDigits(int n) {
        if (n < 10){
            return n;
        }
        String s = Integer.toString(n);
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) < s.charAt(i - 1)){
                int temp = i - 1;
                while (true){
                    if (temp == 0){
                        return n - Integer.parseInt(s.substring(1)) - 1;
                    }else if (s.charAt(temp) - s.charAt(temp - 1) >= 1){
                        return n - Integer.parseInt(s.substring(temp + 1)) - 1;
                    }
                    temp--;
                }
            }
        }
        return n;
    }

    /**
     * 官方-贪心
     * @param n
     * @return
     */
    public int monotoneIncreasingDigits2(int n) {
        char[] strN = Integer.toString(n).toCharArray();
        int i = 1;
        while (i < strN.length && strN[i - 1] <= strN[i]) {
            i += 1;
        }
        if (i < strN.length) {
            while (i > 0 && strN[i - 1] > strN[i]) {
                strN[i - 1] -= 1;
                i -= 1;
            }
            for (i += 1; i < strN.length; ++i) {
                strN[i] = '9';
            }
        }
        return Integer.parseInt(new String(strN));
    }
}
